<?php
/*
 * 打印N个数组整体最大的Top
 * 【题目】
 * 有N个长度不一的数组，所有的数组都是有序的，
 * 请从大到小打印这N个数组整体最大的前K个数。
 * 例如，
 * 输入含有N行元素的二维数组可以代表N个一维数组。
 * 219,405,538,845,971
 * 148,558
 * 52,99,348,691
 * 再输入整数k=5，则打印：Top 5:
 * 971,845,691,558,538
 * 【要求】
 * 1．如果所有数组的元素个数小于K，则从大到小打印所有的数。
 * 2．要求时间复杂度为O(KlogN)
 */

$matrix = [
    [219,405,538,845,971],
    [148,558],
    [52,99,348,691],
];
$k = 5;
$obj = new Code_02_TopK();
$obj->main($matrix, $k);

class HeapNode
{
    public $value;      //值
    public $arrNum;     //来自哪个数组
    public $index;      //所在数组的key

    public function __construct($value, $arrNum, $index)
    {
        $this->index = $index;
        $this->arrNum = $arrNum;
        $this->value = $value;
    }
}

class Code_02_TopK
{
    public function main($matrix, $k)
    {
        $heapSize = count($matrix);
        $heapArr = [];
        for ($i = 0; $i < $heapSize; $i++) {
            $index = count($matrix[$i]) - 1;
            // 把每个数组最后的数先放入大顶堆中
            $heapArr[$i] = new HeapNode($matrix[$i][$index], $i, $index);
            // 新建节点时维护大根堆
            $this->_heapInsert($heapArr, $i);
        }
        for ($i = 0; $i < $k; $i++) {
            if ($heapSize == 0) {
                break;
            }
            echo $heapArr[0]->value .' ';
            // 找到堆顶元素所在数组的index
            if ($heapArr[0]->index != 0) {
                // 如果不是所在数组的第一个元素，往前找元素替换掉堆顶的node
                $heapArr[0]->value = $matrix[$heapArr[0]->arrNum][--$heapArr[0]->index];
            } else {
                // 将头节点和第$heapSize交换，然后将heapArr的越界标志更新为减一的$heapSize，大于等于这个heapSize的都视为无效的堆
                $this->swap($heapArr, 0, --$heapSize);
            }
            $this->_heapify($heapArr, 0, $heapSize);
        }
    }

    // 新建节点时维护大顶堆
    protected function _heapInsert(&$heapArr, $i)
    {
        while ($i != 0) {
            $parent = intval(($i - 1) / 2);
            //父元素的值比当前元素的小，交换
            if ($heapArr[$parent]->value < $heapArr[$i]->value) {
                $this->swap($heapArr, $i, $parent);
                $i = $parent;
            } else {
                break;
            }
        }
    }

    protected function swap(&$heapArr, $key1, $key2)
    {
        $tmp = $heapArr[$key1];
        $heapArr[$key1] = $heapArr[$key2];
        $heapArr[$key2] = $tmp;
    }

    // 维护大顶堆结构，在这个题目heapSize会慢慢缩小
    protected function _heapify(&$heapArr, $index, $heapSize)
    {
        $left = $index * 2 + 1;
		$right = $index * 2 + 2;
		$largest = $index;
		while ($left < $heapSize) {
		    // 找到左右孩子里自己的值大且是值最大的节点 存在的话则交换
            if ($heapArr[$left]->value > $heapArr[$index]->value) {
                $largest = $left;
            }
            if ($right < $heapSize && $heapArr[$right]->value > $heapArr[$largest]->value) {
                $largest = $right;
            }
            if ($largest != $index) {
                $this->swap($heapArr, $largest, $index);
            } else {
                break;
            }
            $index = $largest;
            $left = $index * 2 + 1;
            $right = $index * 2 + 2;
        }
    }
}